package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         47,
		Discription: "存在重复的数组的排列组合",
		Level:       3,
		Labels: map[string]int{
			"递归":   1,
			"空间复用": 1,
			"去重":   1,
			"哈希表":   1,
		},
	})
}

func PermuteUnique(nums []int) [][]int {
	res := make([][]int, 0)
	var travel func(int)
	travel = func(start int) {
		if start == len(nums) {
			res = append(res, append([]int(nil), nums...))
			return
		}

		valMap := make(map[int]bool, 0)
		for i := start; i < len(nums); i++ {
			if valMap[nums[i]] {
				continue
			}

			//在每次递归时，维护一个哈希表，记录已在该位置遍历过的数字，回溯的时候不需要重置为false
			valMap[nums[i]] = true
			nums[start], nums[i] = nums[i], nums[start]
			travel(start + 1)
			nums[start], nums[i] = nums[i], nums[start]
		}
	}

	travel(0)
	return res
}
